Vickrey–Clarke–Groves auction

A Vickrey–Clarke–Groves (VCG) auction of multiple goods is a sealed-bid auction wherein bidders report their valuations for the items. The auction system assigns the items in a socially optimal manner, while ensuring each bidder receives at most one item. This system charges each individual the harm they cause to other bidders,^[1] and ensures that the optimal strategy for a bidder is to bid the true valuations of the objects. It is a generalization of a Vickrey auction for multiple items.

The auction is named after William Vickrey, Edward H. Clarke, and Theodore Groves.

1 A Formal Description
2 Examples
- 2.1 Example #1
- 2.2 Example #2
3 Optimality of Truthful Bidding
4 More general setting
5 References

A Formal Description

For any set of auctioned items $M = \{t_1,\ldots,t_m\}$ and a set of bidders $N = \{b_1,\ldots,b_n\}$ , let $V^M_N$ the social value of the VCG auction for a given bid-combination. A bidder $b_i$ who wins an item $t_j$ pays $V^{M}_{N \setminus \{b_i\}}-V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}$ , which is the social cost of his winning that is incurred by the rest of the agents

Indeed, the set of bidders other than $\{b_i\}$ is $N \setminus \{b_i\}$ . When item $t_j$ is available, they could attain welfare $V^{M}_{N \setminus \{b_i\}}.$ The winning of the item by $b_i$ reduces the set of available items to $M \setminus \{t_j\}$ , however, so that the attainable welfare is now $V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}$ . The difference between the two levels of welfare is the payment for $t_j$ paid by the winning bidder $b_i$ .

The winning bidder who has value $A$ for the item $t_j$ derives therefore utility $A - \left(V^{M}_{N \setminus \{b_i\}}-V^{M \setminus \{t_j\}}_{N \setminus \{b_i\}}\right).$

Examples

Example #1

See the example with apples in the introduction of Vickrey Auction.

Example #2

Assume that there are two bidders, $b_1$ and $b_2$ , two items, $t_1$ and $t_2$ , and each bidder is allowed to obtain one item. We let $v_{i,j}$ be bidder $b_i$ 's valuation for item $t_j$ . Assume $v_{1,1} = 10$ , $v_{1,2} = 5$ , $v_{2,1} = 5$ , and $v_{2,2} = 3$ . We see that both $b_1$ and $b_2$ would prefer to receive item $t_1$ ; however, the socially optimal assignment gives item $t_1$ to bidder $b_1$ (so his achieved value is $10$ ) and item $t_2$ to bidder $b_2$ (so his achieved value is $3$ ). Hence, the total achieved value is $13$ , which is optimal.

If person $b_2$ were not in the auction, person $b_1$ would still be assigned to $t_1$ , and hence no harm was done for that bidder. Hence, $b_2$ is charged nothing.

If person $b_1$ were not in the auction, person $b_2$ would be assigned to $t_1$ , and would have valuation $5$ . $b_1$ thus caused $2$ harm to $b_2$ , and hence $b_1$ is charged $2$ .

Optimality of Truthful Bidding

The following is a proof that bidding one's true valuations for the auctioned items is optimal^[2]

For each bidder $b_i$ , let $v_i$ be her true valuation of an item $t_i$ , and suppose (without loss of generality) that $b_1$ wins $t_1$ upon submitting his true valuations.

Note that the size bid of $b_1$ has no effect on her utility as long as she wins the item (see the utility function above). Hence, we assume that $b_1$ does not bid truthfully, and receives item $t_j$ because of his non-truthful bidding. In the truthful bidding case, $b_1$ has total utility $U_1 = v_1-\left(V^{M}_{N \setminus \{b_1\}}-V^{M \setminus \{t_1\}}_{N \setminus \{b_1\}}\right)$ . In the untruthful bidding case, $b_1$ has total utility $U_2 = v_j-\left(V^{M}_{N \setminus \{b_1\}}-V^{M \setminus \{t_j\}}_{N \setminus \{b_1\}}\right)$ . Hence, we must prove that $U_1 - U_2 \geq 0$ , which shows that the utility received from truthful bidding is always at least that received from untruthful bidding.

$U_1 - U_2 = v_1 - \left(V^{M}_{N \setminus \{b_1\}} - V^{M \setminus \{t_1\}}_{N \setminus \{b_1\}}\right) - v_j %2B \left(V^{M}_{N \setminus \{b_1\}}-V^{M \setminus \{t_j\}}_{N \setminus \{b_1\}}\right) = \left[v_1 %2B V^{M \setminus \{t_1\}}_{N \setminus \{b_1\}}\right] - \left[v_j %2B V^{M \setminus \{t_j\}}_{N \setminus \{b_1\}}\right]$

However, the first term there is the maximum total social value achieved when $b_1$ received $t_1$ , and the second term there is the maximum total social value achieved when $b_1$ received $t_j$ . However, we assumed that the VCG auction gave $b_1$ item $t_1$ ; hence, the first term must be greater, and $U_1 - U_2 \geq 0$ .

More general setting

We can consider a more general setting^[3] of the VCG mechanism. Consider a set $A$ of possible outcomes and $n$ bidders which have different valuations for each outcome. This can be expressed as, function

$v_i�: A \longrightarrow R_%2B$

for each bidder $i$ which expresses the value it has for each alternative. In this auction, each bidder will submit his valuation and the VCG mechanism will choose the alternative $a \in A$ that maximizes $\sum_i v_i(a)$ and charge prices $p_i$ given by:

$p_i = h_i(v_{-i}) - \sum_{j \neq i} v_j(a)$

where $v_{-i} = (v_1, \dots, v_{i-1}, v_{i%2B1}, \dots, v_n)$ , that is, $h_i$ is a function that only depends on the valuation of the other players. This alone gives a truthful mechanism, that is, a mechanism where bidding the true valuation is a dominant strategy.

We could take, for example, $h_i(v_{-i}) = 0$ , but we would have all prices negative, what might not be desirable - we would rather prefer that players give money to the mechanism than the other way round. The function:

$h_i(v_{-i}) = \max_{b \in A} \sum_{j \neq i} v_j(b)$

is called Clarke pivot rule. It has some very good properties as:

it is individually rational, i.e., $v_i (a) - p_i \geq 0$ . It means that all the players are getting positive utility by participating in the auction. No one is really being forced do bid.

it has no positive transfers, i.e., $p_i \geq 0$ . So the mechanism doesn't need to pay anything to the bidders.

References

^ von Ahn, Luis (2008-10-07). "Sponsored Search" (PDF). 15–396: Science of the Web Course Notes. Carnegie Mellon University. http://scienceoftheweb.org/15-396/lectures/lecture11.pdf. Retrieved 2008-11-05.
^ von Ahn, Luis (2008-10-07). "Assignment 5 Solutions" (PDF). 15–396: Science of the Web Published Solutions. Carnegie Mellon University. http://www.scienceoftheweb.org/15-396/assignments/assignment5_solutions.pdf. Retrieved 2008-11-05.
^ Nisan, Roughgarden, Tardos and Vazirani, Algorithmic Game Theory, Cambridge, 2007